package class_4;

import java.util.Random;
/**
 * 最长有效括号
 * 测试链接: https://leetcode.com/problems/longest-valid-parentheses/description/
 *   // dp[0...n-1]
 *   // dp[i] : 子串必须以i位置的字符结尾的情况下，往左整体有效的最大长度
 */
public class Coding_longestValidParentheses {
	public static int end;
	public static int length;
	public static int longestValidParentheses(String str) {
        if (str == null || str.length() < 1) {
            return 0;
        }
        // 字符串转字符数组
        char[] s = str.toCharArray();

        // 申请一个一维缓存表， 动态规划启动。
        int[] dp = new int[s.length];// dp[0....n-1]==0
        int ans = 0;
        for (int i = 1, p; i < s.length; i++) {
            // 左括号必定无法匹配
            if (s[i] == ')') {
                p = i - dp[i - 1] - 1;// 后撤步
                if (p >= 0 && s[p] == '(') {
                    dp[i] = dp[i - 1] + 2 + (p - 1 >= 0 ? dp[p - 1] : 0);
                }
                if(dp[i] > ans) {
                	ans = dp[i];
                	end = i;
                }
            }
        }
        length = ans;
        return ans;
    }
	public static int MAX = 100;
	public static char[] charArray = new char[MAX];
	public static int n;
	public static int random() {
		return (int)(Math.random() * MAX);//生成字符数组实际的有效长度。
	}
	public static void main(String[] args) {
		n = random();//字符数组长度
		Random rand = new Random();
		for(int i=0;i<n;i++) {
			charArray[i] = rand.nextInt(0,2) == 0 ? '(':')';
		}
		String str = new String(charArray, 0, n);
		System.out.printf("字符串长度: %d\n", n);
		System.out.printf("下标对应:");
		n = n>=50?50:n;
		for(int i =0;i<n;i++) {
			System.out.printf("%-2d",i);
		}
		System.out.println();
		String s2 = (str.length()>=50?str.substring(0,51)+"...":str);
		System.out.print("原字符串:");
		for(int j=0;j<s2.length();j++) {
			System.out.printf("%c ", s2.charAt(j));
		}
		System.out.println();
		int ret = longestValidParentheses(str);
		System.out.println("最长有效长度括号字符串实际长度:"+ret);
		System.out.println("初始下标:"+(end-length+1));
		System.out.println("结束下标:"+(end));
		System.out.println("合计长度:"+length);
		System.out.println("子串:"+str.substring(end-length+1, end+1));
	}
}
